{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #魔法棋盘"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getSchemeCount"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #魔法棋盘"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "在大小为 `n * m` 的棋盘中，有两种不同的棋子：黑色，红色。当两颗颜色不同的棋子同时满足以下两种情况时，将会产生魔法共鸣：\n",
    "- 两颗异色棋子在同一行或者同一列\n",
    "- 两颗异色棋子之间恰好只有一颗棋子\n",
    "    > 注：异色棋子之间可以有空位\n",
    "\n",
    "由于棋盘上被施加了魔法禁制，棋盘上的部分格子变成问号。`chessboard[i][j]` 表示棋盘第 `i` 行 `j` 列的状态：\n",
    "- 若为 `.` ，表示当前格子确定为空\n",
    "- 若为 `B` ，表示当前格子确定为 黑棋\n",
    "- 若为 `R` ，表示当前格子确定为 红棋\n",
    "- 若为 `?` ，表示当前格子待定\n",
    "\n",
    "现在，探险家小扣的任务是确定所有问号位置的状态（留空/放黑棋/放红棋），使最终的棋盘上，任意两颗棋子间都 **无法** 产生共鸣。请返回可以满足上述条件的放置方案数量。\n",
    "\n",
    "**示例1：**\n",
    "> 输入：`n = 3, m = 3, chessboard = [\"..R\",\"..B\",\"?R?\"]`\n",
    ">\n",
    "> 输出：`5`\n",
    ">\n",
    "> 解释：给定的棋盘如图：\n",
    ">![image.png](https://pic.leetcode.cn/1681714583-unbRox-image.png){:height=150px}\n",
    "> 所有符合题意的最终局面如图：\n",
    ">![image.png](https://pic.leetcode.cn/1681714596-beaOHK-image.png){:height=150px}\n",
    "\n",
    "**示例2：**\n",
    "> 输入：`n = 3, m = 3, chessboard = [\"?R?\",\"B?B\",\"?R?\"]`\n",
    ">\n",
    "> 输出：`105`\n",
    "\n",
    "**提示：**\n",
    "- `n == chessboard.length`\n",
    "- `m == chessboard[i].length`\n",
    "- `1 <= n*m <= 30`\n",
    "- `chessboard` 中仅包含 `\".\"、\"B\"、\"R\"、\"?\"`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [1ybDKD](https://leetcode.cn/problems/1ybDKD/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [1ybDKD](https://leetcode.cn/problems/1ybDKD/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n3\\n[\"..R\",\"..B\",\"?R?\"]', '3\\n3\\n[\"?R?\",\"B?B\",\"?R?\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSchemeCount(self, n: int, m: int, chessboard: List[str]) -> int:\n",
    "        # n行m列\n",
    "        # 保证m小于n\n",
    "        if m > n:\n",
    "            # 行列交换\n",
    "            n, m = m, n\n",
    "            new = [[0] * m for _ in range(n)]\n",
    "\n",
    "            for i in range(n):\n",
    "                for j in range(m):\n",
    "                    new[i][j] = chessboard[j][i]\n",
    "\n",
    "            chessboard = new\n",
    "\n",
    "        # 动态规划，一行行计算，每一行最多3**m中可能（由于已知+魔法，还会少）\n",
    "        # key: 为前两行每列向上两个棋子\n",
    "        t = tuple([0] * (2 * m))\n",
    "        dp = {t: 1}\n",
    "\n",
    "        # 每行的所有可能性\n",
    "        dv = {\".\": 0, \"B\": 1, \"R\": 2}\n",
    "\n",
    "        def dfs(i, l=[], num1=0, num2=0):\n",
    "            if i == m:\n",
    "                yield l\n",
    "                return\n",
    "\n",
    "            v = dv.get(row[i])\n",
    "            if v == 0:\n",
    "                yield from dfs(i + 1, l + [0], num1, num2)\n",
    "                return\n",
    "\n",
    "            if v == 1:\n",
    "                if num1 != 2:\n",
    "                    yield from dfs(i + 1, l + [1], num2, 1)\n",
    "                return\n",
    "\n",
    "            if v == 2:\n",
    "                if num1 != 1:\n",
    "                    yield from dfs(i + 1, l + [2], num2, 2)\n",
    "                return\n",
    "\n",
    "            # ? 都有可能\n",
    "            yield from dfs(i + 1, l + [0], num1, num2)\n",
    "\n",
    "            if num1 != 2:\n",
    "                yield from dfs(i + 1, l + [1], num2, 1)\n",
    "\n",
    "            if num1 != 1:\n",
    "                yield from dfs(i + 1, l + [2], num2, 2)\n",
    "\n",
    "        for row in chessboard:\n",
    "            now = defaultdict(int)\n",
    "\n",
    "            for l in dfs(0):\n",
    "                for k, num in dp.items():\n",
    "                    # 判断列是否合法\n",
    "                    _k = list(k)\n",
    "\n",
    "                    for j, v in enumerate(l):\n",
    "                        if v == 0:\n",
    "                            continue\n",
    "\n",
    "                        j2 = j + j\n",
    "\n",
    "                        if v == 1:\n",
    "                            if k[j2] == 2:\n",
    "                                break\n",
    "                        elif k[j2] == 1:\n",
    "                            break\n",
    "\n",
    "                        _k[j2], _k[j2 + 1] = _k[j2 + 1], v\n",
    "                    else:\n",
    "                        now[tuple(_k)] += num\n",
    "\n",
    "            # print(now)\n",
    "            dp = now\n",
    "\n",
    "        return sum(dp.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "TRANS = (\n",
    "    # (当前序列末尾添加 B 之后的状态，当前序列末尾添加 R 之后的状态)\n",
    "    (1, 2),   # 0: 空\n",
    "    (3, 6),   # 1: 一个 B\n",
    "    (5, 4),   # 2: 一个 R\n",
    "    (3, -1),  # 3: 连续多个 B\n",
    "    (-1, 4),  # 4: 连续多个 R\n",
    "    (-1, 6),  # 5: BR 交替，且以 B 结尾\n",
    "    (5, -1),  # 6: BR 交替，且以 R 结尾\n",
    ")\n",
    "\n",
    "class Solution:\n",
    "    def getSchemeCount(self, n: int, m: int, a: List[str]) -> int:\n",
    "        if n < m:  # 保证 n >= m\n",
    "            a = [list(col) for col in zip(*a)]\n",
    "            n, m = m, n\n",
    "        @cache\n",
    "        def DFS(r: int, mask: int) -> int:\n",
    "            if r == n:\n",
    "                return 1\n",
    "            # 写一个爆搜，生成出所有的合法状态\n",
    "            def dfs(c: int, row_mask: int, col_mask: int) -> int:\n",
    "                if c == m:\n",
    "                    return DFS(r + 1, col_mask)  # 枚举下一行\n",
    "                def nxt(color: int) -> int:\n",
    "                    rm = TRANS[row_mask][color]  # 新的 rowMask\n",
    "                    if rm < 0: return 0  # 非法\n",
    "                    c3 = c * 3\n",
    "                    cm = TRANS[(col_mask >> c3) & 7][color]  # 新的 colMask 的第 c 列\n",
    "                    if cm < 0: return 0 # 非法\n",
    "                    cm = col_mask & ~(7 << c3) | (cm << c3)  # 修改 colMask 的第 c 列\n",
    "                    return dfs(c + 1, rm, cm)\n",
    "                b = a[r][c]\n",
    "                if b == 'B':\n",
    "                    return nxt(0)\n",
    "                if b == 'R':\n",
    "                    return nxt(1)\n",
    "                if b == '.':\n",
    "                    return dfs(c + 1, row_mask, col_mask)\n",
    "                return dfs(c + 1, row_mask, col_mask) + nxt(0) + nxt(1)\n",
    "            return dfs(0, 0, mask)\n",
    "        return DFS(0, 0)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "TRANS = (\n",
    "    # (当前序列末尾添加 B 之后的状态，当前序列末尾添加 R 之后的状态)\n",
    "    (1, 2),   # 0: 空\n",
    "    (3, 6),   # 1: 一个 B\n",
    "    (5, 4),   # 2: 一个 R\n",
    "    (3, -1),  # 3: 连续多个 B\n",
    "    (-1, 4),  # 4: 连续多个 R\n",
    "    (-1, 6),  # 5: BR 交替，且以 B 结尾\n",
    "    (5, -1),  # 6: BR 交替，且以 R 结尾\n",
    ")\n",
    "\n",
    "class Solution:\n",
    "    def getSchemeCount(self, n: int, m: int, a: List[str]) -> int:\n",
    "        if n < m:  # 保证 n >= m\n",
    "            a = [list(col) for col in zip(*a)]\n",
    "            n, m = m, n\n",
    "        @cache\n",
    "        def DFS(r: int, mask: int) -> int:\n",
    "            if r == n:\n",
    "                return 1\n",
    "            # 写一个爆搜，生成出所有的合法状态\n",
    "            def dfs(c: int, row_mask: int, col_mask: int) -> int:\n",
    "                if c == m:\n",
    "                    return DFS(r + 1, col_mask)  # 枚举下一行\n",
    "                def nxt(color: int) -> int:\n",
    "                    rm = TRANS[row_mask][color]  # 新的 rowMask\n",
    "                    if rm < 0: return 0  # 非法\n",
    "                    c3 = c * 3\n",
    "                    cm = TRANS[(col_mask >> c3) & 7][color]  # 新的 colMask 的第 c 列\n",
    "                    if cm < 0: return 0 # 非法\n",
    "                    cm = col_mask & ~(7 << c3) | (cm << c3)  # 修改 colMask 的第 c 列\n",
    "                    return dfs(c + 1, rm, cm)\n",
    "                b = a[r][c]\n",
    "                if b == 'B':\n",
    "                    return nxt(0)\n",
    "                if b == 'R':\n",
    "                    return nxt(1)\n",
    "                if b == '.':\n",
    "                    return dfs(c + 1, row_mask, col_mask)\n",
    "                return dfs(c + 1, row_mask, col_mask) + nxt(0) + nxt(1)\n",
    "            return dfs(0, 0, mask)\n",
    "        return DFS(0, 0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from functools import cache\n",
    "\n",
    "TRANS = (\n",
    "    # (当前序列末尾添加 B 之后的状态，当前序列末尾添加 R 之后的状态)\n",
    "    (1, 2),   # 0: 空\n",
    "    (3, 6),   # 1: 一个 B\n",
    "    (5, 4),   # 2: 一个 R\n",
    "    (3, -1),  # 3: 连续多个 B\n",
    "    (-1, 4),  # 4: 连续多个 R\n",
    "    (-1, 6),  # 5: BR 交替，且以 B 结尾\n",
    "    (5, -1),  # 6: BR 交替，且以 R 结尾\n",
    ")\n",
    "\n",
    "class Solution:\n",
    "    def getSchemeCount(self, n: int, m: int, a: List[str]) -> int:\n",
    "        if n < m:\n",
    "            a = [list(col) for col in zip(*a)]\n",
    "            n, m = m, n\n",
    "        \n",
    "        @cache\n",
    "        def DFS(r: int, mask: int) -> int:\n",
    "            if r == n:\n",
    "                return 1\n",
    "            \n",
    "            def dfs(c: int, row_mask: int, col_mask: int) -> int:\n",
    "                if c == m:\n",
    "                    return DFS(r + 1, col_mask)\n",
    "                \n",
    "                def nxt(color: int) -> int:\n",
    "                    rm = TRANS[row_mask][color]\n",
    "                    if rm < 0:\n",
    "                        return 0\n",
    "                    c3 = c * 3\n",
    "                    cm = TRANS[(col_mask >> c3) & 7][color]\n",
    "                    if cm < 0:\n",
    "                        return 0\n",
    "                    cm = col_mask & ~(7 << c3) | (cm << c3)\n",
    "                    return dfs(c + 1, rm, cm)\n",
    "                \n",
    "                b = a[r][c]\n",
    "                if b == 'B':\n",
    "                    return nxt(0)\n",
    "                if b == 'R':\n",
    "                    return nxt(1)\n",
    "                if b == '.':\n",
    "                    return dfs(c + 1, row_mask, col_mask)\n",
    "                return dfs(c + 1, row_mask, col_mask) + nxt(0) + nxt(1)\n",
    "            \n",
    "            return dfs(0, 0, mask)\n",
    "        \n",
    "        return DFS(0, 0)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "TRANS = (\n",
    "    # (当前序列末尾添加 B 之后的状态，当前序列末尾添加 R 之后的状态)\n",
    "    (1, 2),   # 0: 空\n",
    "    (3, 6),   # 1: 一个 B\n",
    "    (5, 4),   # 2: 一个 R\n",
    "    (3, -1),  # 3: 连续多个 B\n",
    "    (-1, 4),  # 4: 连续多个 R\n",
    "    (-1, 6),  # 5: BR 交替，且以 B 结尾\n",
    "    (5, -1),  # 6: BR 交替，且以 R 结尾\n",
    ")\n",
    "\n",
    "class Solution:\n",
    "    def getSchemeCount(self, n: int, m: int, a: List[str]) -> int:\n",
    "        if n < m:  # 保证 n >= m\n",
    "            a = [list(col) for col in zip(*a)]\n",
    "            n, m = m, n\n",
    "        @cache\n",
    "        def DFS(r: int, mask: int) -> int:\n",
    "            if r == n:\n",
    "                return 1\n",
    "            # 写一个爆搜，生成出所有的合法状态\n",
    "            def dfs(c: int, row_mask: int, col_mask: int) -> int:\n",
    "                if c == m:\n",
    "                    return DFS(r + 1, col_mask)  # 枚举下一行\n",
    "                def nxt(color: int) -> int:\n",
    "                    rm = TRANS[row_mask][color]  # 新的 rowMask\n",
    "                    if rm < 0: return 0  # 非法\n",
    "                    c3 = c * 3\n",
    "                    cm = TRANS[(col_mask >> c3) & 7][color]  # 新的 colMask 的第 c 列\n",
    "                    if cm < 0: return 0 # 非法\n",
    "                    cm = col_mask & ~(7 << c3) | (cm << c3)  # 修改 colMask 的第 c 列\n",
    "                    return dfs(c + 1, rm, cm)\n",
    "                b = a[r][c]\n",
    "                if b == 'B':\n",
    "                    return nxt(0)\n",
    "                if b == 'R':\n",
    "                    return nxt(1)\n",
    "                if b == '.':\n",
    "                    return dfs(c + 1, row_mask, col_mask)\n",
    "                return dfs(c + 1, row_mask, col_mask) + nxt(0) + nxt(1)\n",
    "            return dfs(0, 0, mask)\n",
    "        return DFS(0, 0)\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
